#leetcode题目51：n皇后
#难度：困难
#时间复杂度：O(n!)
#空间复杂度：O(n)
#方法：回溯



from typing import List
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col=[0]*n
        ans=[]
        on_path=[False]*n
        dia1=[False]*(2*n-1) #增加斜线攻击的判断
        dia2=[False]*(2*n-1)
        def dfs(r):
            for c in range(n):
                if r==n:
                    ans.append(["."*c+"Q"+"."*(n-c-1) for c in col])
                    return
                if not on_path[c] and not dia1[r+c] and not dia2[r-c]:
                    on_path[c]=dia1[r+c]=dia2[r-c]=True
                    col[r]=c
                    dfs(r+1)
                    on_path[c]=dia1[r+c]=dia2[r-c]=False

        dfs(0)
        return ans


#测试数据
n=4
#预期输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
solution=Solution()
print(solution.solveNQueens(n))

